/*
** This file contains low-level memory allocation drivers for when APPID will use the standard C-library malloc/realloc/free interface
** to obtain the memory it needs while adding lots of additional debugging information to each allocation in order to help detect and fix memory
** leaks and memory usage errors.
**
** This file contains implementations of the low-level memory allocation routines specified in the sqlite3_mem_methods object.
*/
#include "System.h"

/*
** This version of the memory allocator is used only if the SYSTEM_MEMDEBUG macro is defined
*/
#ifdef SYSTEM_MEMDEBUG

/*
** The backtrace functionality is only available with GLIBC
*/
#ifdef __GLIBC__
extern int backtrace(void**,int);
extern void backtrace_symbols_fd(void*const*,int,int);
#else
# define backtrace(A,B) 1
# define backtrace_symbols_fd(A,B,C)
#endif
#include <stdio.h>

/*
** Each memory allocation looks like this:
**
**  ------------------------------------------------------------------------
**  | Title |  backtrace pointers |  MemBlockHdr |  allocation |  EndGuard |
**  ------------------------------------------------------------------------
**
** The application code sees only a pointer to the allocation.  We have to back up from the allocation pointer to find the MemBlockHdr.  The
** MemBlockHdr tells us the size of the allocation and the number of backtrace pointers.  There is also a guard word at the end of the
** MemBlockHdr.
*/
struct MemBlockHdr
{
	i64 iSize;                          /* Size of this allocation */
	struct MemBlockHdr *pNext, *pPrev;  /* Linked list of all unfreed memory */
	char nBacktrace;                    /* Number of backtraces on this alloc */
	char nBacktraceSlots;               /* Available backtrace slots */
	u8 nTitle;                          /* Bytes of title; includes '\0' */
	u8 eType;                           /* Allocation type code */
	int iForeGuard;                     /* Guard word for sanity */
};

/*
** Guard words
*/
#define FOREGUARD 0x80F5E153
#define REARGUARD 0xE4676B53

/*
** Number of malloc size increments to track.
*/
#define NCSIZE  1000

/*
** All of the static variables used by this module are collected into a single structure named "mem".  This is to keep the
** static variables organized and to reduce namespace pollution when this module is combined with other in the amalgamation.
*/
static struct
{
	/*
	** Mutex to control access to the memory allocation subsystem.
	*/
	system_mutex *mutex;
	/*
	** Head and tail of a linked list of all outstanding allocations
	*/
	struct MemBlockHdr *pFirst;
	struct MemBlockHdr *pLast;
	/*
	** The number of levels of backtrace to save in new allocations.
	*/
	int nBacktrace;
	void (*xBacktrace)(int, int, void **);
	/*
	** Title text to insert in front of each block
	*/
	int nTitle;        /* Bytes of zTitle to save.  Includes '\0' and padding */
	char zTitle[100];  /* The title text */
	/* 
	** systemMallocDisallow() increments the following counter.
	** systemMallocAllow() decrements it.
	*/
	int disallow; /* Do not allow memory allocation */
	/*
	** Gather statistics on the sizes of memory allocations. nAlloc[i] is the number of allocation attempts of i*8
	** bytes.  i == NCSIZE is the number of allocation attempts for sizes more than NCSIZE*8 bytes.
	*/
	int nAlloc[NCSIZE];      /* Total number of allocations */
	int nCurrent[NCSIZE];    /* Current number of allocations */
	int mxCurrent[NCSIZE];   /* Highwater mark for nCurrent */
} mem;

/*
** Adjust memory usage statistics
*/
static void adjustStats(int iSize, int increment)
{
	int i = ROUND8(iSize)/8;
	if (i > NCSIZE-1)
		i = NCSIZE - 1;
	if (increment > 0)
	{
		mem.nAlloc[i]++;
		mem.nCurrent[i]++;
		if (mem.nCurrent[i]>mem.mxCurrent[i])
			mem.mxCurrent[i] = mem.nCurrent[i];
	}
	else
	{
		mem.nCurrent[i]--;
		assert(mem.nCurrent[i] >= 0);
	}
}

/*
** Given an allocation, find the MemBlockHdr for that allocation.
**
** This routine checks the guards at either end of the allocation and if they are incorrect it asserts.
*/
static struct MemBlockHdr *systemMemsysGetHeader(void *pAllocation)
{
	struct MemBlockHdr *p;
	int *pInt;
	u8 *pU8;
	int nReserve;
	p = (struct MemBlockHdr*)pAllocation;
	p--;
	assert(p->iForeGuard == (int)FOREGUARD);
	nReserve = ROUND8(p->iSize);
	pInt = (int*)pAllocation;
	pU8 = (u8*)pAllocation;
	assert(pInt[nReserve/sizeof(int)] == (int)REARGUARD);
	/* This checks any of the "extra" bytes allocated due to rounding up to an 8 byte boundary to ensure 
	** they haven't been overwritten. */
	while (nReserve-- > p->iSize)
		assert(pU8[nReserve] == 0x65);
	return p;
}

/*
** Return the number of bytes currently allocated at address p.
*/
static int systemMemSize(void *p)
{
	struct MemBlockHdr *pHdr;
	if (!p)
		return 0;
	pHdr = systemMemsysGetHeader(p);
	return pHdr->iSize;
}

/*
** Initialize the memory allocation subsystem.
*/
static int systemMemInit(void *NotUsed)
{
	UNUSED_PARAMETER(NotUsed);
	assert((sizeof(struct MemBlockHdr)&7) == 0);
	if (!systemGlobalConfig.bMemstat )
		/* If memory status is enabled, then the malloc.c wrapper will already hold the STATIC_MEM mutex when the routines here are invoked. */
		mem.mutex = systemMutexAlloc(SYSTEM_MUTEX_STATIC_MEM);
	return SYSTEM_OK;
}

/*
** Deinitialize the memory allocation subsystem.
*/
static void systemMemShutdown(void *NotUsed)
{
	UNUSED_PARAMETER(NotUsed);
	mem.mutex = 0;
}

/*
** Round up a request size to the next valid allocation size.
*/
static int systemMemRoundup(int n)
{
  return ROUND8(n);
}

/*
** Fill a buffer with pseudo-random bytes.  This is used to preset the content of a new memory allocation to unpredictable values and
** to clear the content of a freed allocation to unpredictable values.
*/
static void randomFill(char *pBuf, int nByte)
{
	unsigned int x, y, r;
	x = SYSTEM_PTR_TO_INT(pBuf);
	y = nByte | 1;
	while (nByte >= 4)
	{
		x = (x>>1) ^ (-(x&1) & 0xd0000001);
		y = y*1103515245 + 12345;
		r = x ^ y;
		*(int*)pBuf = r;
		pBuf += 4;
		nByte -= 4;
	}
	while (nByte-- > 0)
	{
		x = (x>>1) ^ (-(x&1) & 0xd0000001);
		y = y*1103515245 + 12345;
		r = x ^ y;
		*(pBuf++) = r & 0xff;
	}
}

/*
** Allocate nByte bytes of memory.
*/
static void *systemMemMalloc(int nByte)
{
	struct MemBlockHdr *pHdr;
	void **pBt;
	char *z;
	int *pInt;
	void *p = 0;
	int totalSize;
	int nReserve;
	system_mutex_enter(mem.mutex);
	assert(mem.disallow == 0);
	nReserve = ROUND8(nByte);
	totalSize = nReserve + sizeof(*pHdr) + sizeof(int) + mem.nBacktrace*sizeof(void*) + mem.nTitle;
	p = malloc(totalSize);
	if (p)
	{
		z = (char *)p;
		pBt = (void**)&z[mem.nTitle];
		pHdr = (struct MemBlockHdr*)&pBt[mem.nBacktrace];
		pHdr->pNext = 0;
		pHdr->pPrev = mem.pLast;
		if (mem.pLast)
			mem.pLast->pNext = pHdr;
		else
			mem.pFirst = pHdr;
		mem.pLast = pHdr;
		pHdr->iForeGuard = FOREGUARD;
		pHdr->eType = MEMTYPE_HEAP;
		pHdr->nBacktraceSlots = mem.nBacktrace;
		pHdr->nTitle = mem.nTitle;
		if (mem.nBacktrace)
		{
			void *aAddr[40];
			pHdr->nBacktrace = backtrace(aAddr, mem.nBacktrace+1)-1;
			memcpy(pBt, &aAddr[1], pHdr->nBacktrace*sizeof(void*));
			assert(pBt[0]);
			if (mem.xBacktrace)
				mem.xBacktrace(nByte, pHdr->nBacktrace-1, &aAddr[1]);
		}
		else
			pHdr->nBacktrace = 0;
		if (mem.nTitle)
			memcpy(z, mem.zTitle, mem.nTitle);
		pHdr->iSize = nByte;
		adjustStats(nByte, +1);
		pInt = (int*)&pHdr[1];
		pInt[nReserve/sizeof(int)] = REARGUARD;
		randomFill((char*)pInt, nByte);
		memset(((char*)pInt)+nByte, 0x65, nReserve-nByte);
		p = (void*)pInt;
	}
	system_mutex_leave(mem.mutex);
	return p; 
}

/*
** Free memory.
*/
static void systemMemFree(void *pPrior)
{
	struct MemBlockHdr *pHdr;
	void **pBt;
	char *z;
	assert(systemGlobalConfig.bMemstat || systemGlobalConfig.bCoreMutex == 0 || mem.mutex != 0);
	pHdr = systemMemsysGetHeader(pPrior);
	pBt = (void**)pHdr;
	pBt -= pHdr->nBacktraceSlots;
	system_mutex_enter(mem.mutex);
	if (pHdr->pPrev)
	{
		assert(pHdr->pPrev->pNext == pHdr);
		pHdr->pPrev->pNext = pHdr->pNext;
	}
	else
	{
		assert(mem.pFirst == pHdr);
		mem.pFirst = pHdr->pNext;
	}
	if (pHdr->pNext)
	{
		assert(pHdr->pNext->pPrev == pHdr);
		pHdr->pNext->pPrev = pHdr->pPrev;
	}
	else
	{
		assert(mem.pLast == pHdr);
		mem.pLast = pHdr->pPrev;
	}
	z = (char*)pBt;
	z -= pHdr->nTitle;
	adjustStats(pHdr->iSize, -1);
	randomFill(z, sizeof(void*)*pHdr->nBacktraceSlots + sizeof(*pHdr) + pHdr->iSize + sizeof(int) + pHdr->nTitle);
	free(z);
	system_mutex_leave(mem.mutex);  
}

/*
** Change the size of an existing memory allocation.
**
** For this debugging implementation, we *always* make a copy of the allocation into a new place in memory.  In this way, if the 
** higher level code is using pointer to the old allocation, it is much more likely to break and we are much more liking to find
** the error.
*/
static void *systemMemRealloc(void *pPrior, int nByte)
{
	struct MemBlockHdr *pOldHdr;
	void *pNew;
	assert(mem.disallow == 0);
	assert((nByte & 7) == 0);     /* EV: R-46199-30249 */
	pOldHdr = systemMemsysGetHeader(pPrior);
	pNew = systemMemMalloc(nByte);
	if (pNew)
	{
		memcpy(pNew, pPrior, nByte<pOldHdr->iSize ? nByte : pOldHdr->iSize);
		if (nByte>pOldHdr->iSize)
			randomFill(&((char*)pNew)[pOldHdr->iSize], nByte - pOldHdr->iSize);
		systemMemFree(pPrior);
	}
	return pNew;
}

/*
** Populate the low-level memory allocation function pointers in systemGlobalConfig.m with pointers to the routines in this file.
*/
void systemMemSetDefault(void)
{
	static const system_mem_methods defaultMethods = {
		systemMemMalloc,
		systemMemFree,
		systemMemRealloc,
		systemMemSize,
		systemMemRoundup,
		systemMemInit,
		systemMemShutdown,
		0 };
	system_config(SYSTEM_CONFIG_MALLOC, &defaultMethods);
}

/*
** Set the "type" of an allocation.
*/
void systemMemdebugSetType(void *p, u8 eType)
{
  if( p && sqlite3GlobalConfig.m.xMalloc==sqlite3MemMalloc ){
    struct MemBlockHdr *pHdr;
    pHdr = sqlite3MemsysGetHeader(p);
    assert( pHdr->iForeGuard==FOREGUARD );
    pHdr->eType = eType;
  }
}

/*
** Return TRUE if the mask of type in eType matches the type of the allocation p.  Also return true if p==NULL.
**
** This routine is designed for use within an assert() statement, to verify the type of an allocation.  For example:
**
**     assert(systemMemdebugHasType(p, MEMTYPE_DB));
*/
int systemMemdebugHasType(void *p, u8 eType)
{
	int rc = 1;
	if (p && systemGlobalConfig.m.xMalloc == systemMemMalloc)
	{
		struct MemBlockHdr *pHdr;
		pHdr = sqlite3MemsysGetHeader(p);
		assert(pHdr->iForeGuard == FOREGUARD);         /* Allocation is valid */
		if ((pHdr->eType&eType) == 0)
			rc = 0;
	}
	return rc;
}

/*
** Return TRUE if the mask of type in eType matches no bits of the type of the allocation p.  Also return true if p == NULL.
**
** This routine is designed for use within an assert() statement, to verify the type of an allocation.  For example:
**
**     assert(systemMemdebugNoType(p, MEMTYPE_DB));
*/
int systemMemdebugNoType(void *p, u8 eType)
{
	int rc = 1;
	if (p && systemGlobalConfig.m.xMalloc == systemMemMalloc)
	{
		struct MemBlockHdr *pHdr;
		pHdr = systemMemsysGetHeader(p);
		assert(pHdr->iForeGuard == FOREGUARD);         /* Allocation is valid */
		if ((pHdr->eType&eType) != 0)
			rc = 0;
	}
	return rc;
}

/*
** Set the number of backtrace levels kept for each allocation. A value of zero turns off backtracing.  The number is always rounded
** up to a multiple of 2.
*/
void systemMemdebugBacktrace(int depth)
{
	if (depth < 0)
		depth = 0;
	else if (depth > 20)
		depth = 20;
	depth = (depth+1)&0xfe;
	mem.nBacktrace = depth;
}

void systemMemdebugBacktraceCallback(void (*xBacktrace)(int, int, void **))
{
	mem.xBacktrace = xBacktrace;
}

/*
** Set the title string for subsequent allocations.
*/
void systemMemdebugSettitle(const char *zTitle)
{
	unsigned int n = systemStrlen30(zTitle) + 1;
	system_mutex_enter(mem.mutex);
	if (n >= sizeof(mem.zTitle))
		n = sizeof(mem.zTitle)-1;
	memcpy(mem.zTitle, zTitle, n);
	mem.zTitle[n] = 0;
	mem.nTitle = ROUND8(n);
	system_mutex_leave(mem.mutex);
}

void systemMemdebugSync()
{
	struct MemBlockHdr *pHdr;
	for (pHdr = mem.pFirst; pHdr; pHdr = pHdr->pNext)
	{
		void **pBt = (void**)pHdr;
		pBt -= pHdr->nBacktraceSlots;
		mem.xBacktrace(pHdr->iSize, pHdr->nBacktrace-1, &pBt[1]);
	}
}

/*
** Open the file indicated and write a log of all unfreed memory allocations into that log.
*/
void systemMemdebugDump(const char *zFilename)
{
	FILE *out;
	struct MemBlockHdr *pHdr;
	void **pBt;
	int i;
	out = fopen(zFilename, "w");
	if (out == 0)
	{
		fprintf(stderr, "** Unable to output memory debug output log: %s **\n", zFilename);
		return;
	}
	for (pHdr = mem.pFirst; pHdr; pHdr = pHdr->pNext)
	{
		char *z = (char*)pHdr;
		z -= pHdr->nBacktraceSlots*sizeof(void*) + pHdr->nTitle;
		fprintf(out, "**** %lld bytes at %p from %s ****\n",  pHdr->iSize, &pHdr[1], (pHdr->nTitle ? z : "???"));
		if (pHdr->nBacktrace)
		{
			fflush(out);
			pBt = (void**)pHdr;
			pBt -= pHdr->nBacktraceSlots;
			backtrace_symbols_fd(pBt, pHdr->nBacktrace, fileno(out));
			fprintf(out, "\n");
		}
	}
	fprintf(out, "COUNTS:\n");
	for (i = 0; i < NCSIZE-1; i++)
		if (mem.nAlloc[i])
			fprintf(out, "   %5d: %10d %10d %10d\n",  i*8, mem.nAlloc[i], mem.nCurrent[i], mem.mxCurrent[i]);
	if (mem.nAlloc[NCSIZE-1])
		fprintf(out, "   %5d: %10d %10d %10d\n", NCSIZE*8-8, mem.nAlloc[NCSIZE-1], mem.nCurrent[NCSIZE-1], mem.mxCurrent[NCSIZE-1]);
	fclose(out);
}

/*
** Return the number of times systemMemMalloc() has been called.
*/
int systemMemdebugMallocCount()
{
	int i;
	int nTotal = 0;
	for (i = 0; i < NCSIZE; i++)
		nTotal += mem.nAlloc[i];
	return nTotal;
}

#endif /* SYSTEM_MEMDEBUG */
